22_efficiency_de_hachage_et_facteur_de

Définition du facteur de charge ($\lambda$)

Le facteur de charge ($\lambda$)est la métrique centrale déterminant l'efficacité réelle d'un tableau haché. Il mesure à quel point le tableau est rempli, corrélant directement à la probabilité et à la longueur des collisions.

$$ \lambda = \frac{\text{Nombre d’éléments stockés } (N)}{\text{Taille du tableau/emplacements } (M)} $$

Chaînage séparé: $\lambda$ représente la longueur moyenne des listes chaînées (chaînes).
Adressement ouvert (sondage): $\lambda$ représente la saturation du tableau, corrélant directement au nombre attendu de sondagesnécessaires pour trouver un emplacement vide ou un élément spécifique.

Facteur de charge et complexité

Pour atteindre les performances théoriques de type $O(1)$ en cas moyen pour les opérations de recherche, insertion et suppression, le facteur de charge ($\lambda$) doit être constant et généralement faible (par exemple, $< 1,0$ ou $< 0,75$).

Facteur de performance	Cas moyen (valeur cible de $\lambda$)	Pire cas (haut $\lambda$)
Temps de recherche/insertion	$O(1 + \lambda) \approx O(1)$	$O(N)$ (approche la recherche linéaire)
Taux de collision	Faible/gérable	Élevé
Surcharge mémoire	$O(N + M)$	$O(N + M)$

Conséquence clé : Si $M$ est fixe et que $N$ augmente, $\lambda$ croît, ce qui dégrade les performances vers $O(N)$.

Stratégie : gestion de la saturation (re-hachage)

Pour éviter la dégradation des performances due à un $\lambda$ élevé, les tableaux hachés efficaces mettent en œuvre re-hachage (redimensionnement).

Surveillance du seuil: Le système surveille $\lambda$. Si celui-ci dépasse un seuil prédéfini (par exemple, 0,75 pour l'adressage ouvert, ou 2,0 pour le chaînage), le redimensionnement est déclenché.
Expansion: La taille du tableau $M$ est augmentée (par exemple doublée à $M'$).
Répartition: Tous les $N$ éléments existants sont réinsérés dans le nouveau tableau plus grand $M'$, en utilisant éventuellement une nouvelle fonction de hachage (modulo $M'$).

Résultat: $\lambda$ diminue immédiatement, restituant la garantie de performance moyenne de la structure $O(1)$ moyenne. Notez que l'opération de re-hachage coûte temporairement $O(N)$.

📝 Quiz interactif

1. Quel est l'objectif principal du re-hachage d'un tableau haché ?

A) Trier les éléments à l'intérieur du tableau.
B) Réduire le facteur de charge et maintenir une performance moyenne de $O(1)$.
C) Libérer immédiatement les emplacements mémoire inutilisés.
D) Vérifier la corruption des données.

2. Dans un tableau haché utilisant le chaînage séparé, si $N=20$ éléments sont stockés dans $M=10$ emplacements, que représente le facteur de charge $\lambda=2$ ?

A) Le tableau est complètement plein et ne peut pas accepter de nouveaux éléments.
B) Le temps de recherche au pire cas est exactement de 2 comparaisons.
C) La longueur moyenne des listes chaînées (chaînes) est de 2.
D) Au moins un emplacement doit contenir exactement 2 éléments.

3. Un système utilise un tableau haché à adressage ouvert avec $M=10\,000$ emplacements. Il stocke $N=1\,500$ éléments. Quelle est la complexité moyenne attendue pour une recherche ?

A) $O(1)$
B) $O(\log N)$
C) $O(N)$
D) $O(\lambda)$

4. Bien qu'une seule opération de re-hachage coûte $O(N)$, pourquoi le coût amortide l'insertion est toujours considéré comme étant $O(1)$ ?

A) Le coût élevé est peu fréquent et réparti sur de nombreuses insertions peu coûteuses.
B) Le re-hachage n'a lieu que lorsque le tableau est vide.
C) Le coût $O(N)$ est un maximum théorique qui n'arrive jamais en pratique.
D) Les processeurs modernes peuvent effectuer le re-hachage en une seule cycle d'horloge.